package huisu;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
 *
 * candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 *
 * 对于给定的输入，保证和为target 的唯一组合数少于 150 个。
 *
 */
public class leetCode39_combinationSum {

    public static void main(String[] args) {
        leetCode39_combinationSum a = new leetCode39_combinationSum();
        int[] nums = {2,3,6,7};
        a.combinationSum(nums,7);

    }

    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> trace = new ArrayList<>();
        build(candidates,target,trace,0,0);
        return ans;
    }
    
    public void build(int[] candidates, int target,List<Integer> trace,int sum, int start){
        if(sum == target){
            ans.add(new ArrayList<>(trace));
            return;
        }
        if(sum > target){
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] <= target) {
                trace.add(candidates[i]);
                build(candidates, target, trace, sum + candidates[i], i);
                trace.remove(trace.size() - 1);
            }
        }

    }

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates == null || candidates.length == 0) return res;
        List<Integer> trace = new ArrayList<>();
        build2(candidates,target,0,trace,0);
        return res;

    }

    public void build2(int[] candidates,int target,int sum, List<Integer> trace,int start){
        if(sum == target){
            res.add(new ArrayList<>(trace));
            return;
        }
        if(sum > target){
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if(sum + candidates[i] <= target){
                trace.add(candidates[i]);
                build2(candidates,target,sum + candidates[i],trace,i);
                trace.remove(trace.size() - 1);
            }
        }
    }



}
